package leetcode.hot100;

@SuppressWarnings("all")
public class _53_最大子序和 {

    // 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
    // 输出：6 --- 因为连续子数组 [4,-1,2,1] 的和最大，为 6
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        // 记录以每个数字结尾的最大子序列和，再从这些子序列和中找出最大子序列和
        int[] dp = new int[nums.length];
        int maxSubSum = nums[0];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            maxSubSum = Math.max(maxSubSum, dp[i]);
        }
        return maxSubSum;
    }
}
